
import java.util.*;

//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {
    //深度优先遍历
    public static void printDFS(TreeNode root) {
        if (root == null) {
            return;
        }
        //前序遍历方式
        System.out.println(root.value);
        printDFS(root.left);
        printDFS(root.right);
    }

    //广度优先遍历
    public static List<List<Integer>> printBFS(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        //queue
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            //先将节点pull出来
            int currentSize = queue.size();  //拿到当前的大小
            List<Integer> templist = new ArrayList<>();
            while (currentSize-- > 0) {
                TreeNode node = queue.poll();
                templist.add(node.value);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            list.add(templist);
        }
        return list;
    }


    public static void quickSort(int[] arr, int start, int end) {
        if (start >= end) return;

        // 三数取中法选择基准
//        int mid = start + (end - start) / 2;
//        if (arr[start] > arr[end]) swap(arr, start, end);
//        if (arr[mid] > arr[end]) swap(arr, mid, end);
//        if (arr[start] < arr[mid]) swap(arr, start, mid);

        int base = arr[start];
        int i = start, j = end;
        while (i < j) {
            while (i < j && arr[j] >= base) j--;

            if (i < j) arr[i++] = arr[j];

            while (i < j && arr[i] <= base) i++;

            if (i < j) arr[j--] = arr[i];
        }
        arr[i] = base;
        quickSort(arr, start, i - 1);
        quickSort(arr, i + 1, end);
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public int lengthOfLongestSubstring(String s) {
        int i = 0, j = 0;
        Set<Character> set = new HashSet<>();
        int maxLen = 0;
        while (j < s.length()) {
            char c = s.charAt(j);
            while (set.contains(c)) {
                set.remove(s.charAt(i));
                i++;
            }
            maxLen = Math.max(maxLen, j - i + 1);
            j++;
            set.add(c);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        int arr[] = {2, 5, 4, 8, 9, 10, 3};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));

    }

    //给一颗二叉树 判断是否是完全二叉树  完全二叉树和慢二叉树不同的概念
//    public boolean isCompleteTree(TreeNode root) {
//         Queue<Pair> queue=new ArrayDeque<>();
//
//    }
    class Pair {
        public TreeNode node;
        public int index;

        public Pair(TreeNode node, int index) {
            this.node = node;
            this.index = index;
        }
    }

    public int climbStairs(int n) {
        if (n==1 ||n==2){
            return n ;
        }

         int dp[]=new int[n+1];
         dp[1]=1;
         dp[2]=1;
        for (int i = 3; i <=n ; i++) {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }

    public int minCostClimbingStairs(int[] cost) {
       int n=cost.length;
        int dp[]=new int[n+1];
        dp[0]=dp[1]=0;
        for (int i = 2; i <n ; i++) {
            dp[i]=Math.max(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[n];
    }
  //如果包含了x-1 会从x-1开始算起  就不用再计算x开始的了
    public int longestConsecutive(int[] nums) {
      Set<Integer> set=new HashSet<>();
      for(Integer x:nums){
          set.add(x);
      }
      int maxLen=0;
      for(Integer x:set){
          //下一个出现的数字
          if(!set.contains(x-1)){
              int cur=x+1;
              //长度为1
              int tempLen=1;
              while (set.contains(cur)){
                  cur++;
                  tempLen++;
              }
              maxLen=Math.max(maxLen, tempLen);
          }
      }
      return maxLen;
    }

    public void moveZeroes(int[] nums) {
        //双指针  j遍历不为0的  i是慢指针  如果不为0就和i进行交换  然后再往后移动
        int n = nums.length;
        int i=0;
        for (int j = 0; j < n; j++) {
            if (nums[j] != 0) {
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
                i++;
            }
        }
    }

    //盛水最多的容器  使用双指针来遍历
    public int maxArea(int[] height) {
       int i=0;
       int j=height.length-1;
       int maxWater=-1;
       while (i<j){
           //取最小的高度
           int minHeight=Math.min(height[i],height[j]);
           maxWater=Math.max(maxWater,minHeight*(j-i+1));

           //需要来移动谁
          if (height[i]<height[j]){
              i++;
          }else{
              j--;
          }
       }
       return maxWater;
    }

    //三数之和
    public List<List<Integer>> threeSuma(int[] nums) {
        int n=nums.length;
        Arrays.sort(nums);
        List<List<Integer>> result=new ArrayList<>();
        for (int i = 0; i < n-1; i++) {
            if (nums[i]>0){
                continue;
            }
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int left=i+1;
            int right=n-1;
            while (left<right){
                int  leftValue=nums[left];
                int  rightValue=nums[right];
                if(nums[i]+leftValue+rightValue==0){
                    List<Integer> temp=new ArrayList<>();
                    temp.add(nums[i]);
                    temp.add(nums[left]);
                    temp.add(nums[right]);
                    result.add(temp);
                    left++;
                    right--;
                    while (left<right&&nums[left]==nums[left-1]){
                        left++;
                    }
                    while (left<right&&nums[right]==nums[right+1]){
                        right--;
                    }
                }else if (nums[i]+leftValue+rightValue>0){
                    right--;
                }else{
                    left++;
                }
            }
        }
        return result;
    }

    public int lengthOfLongestSubstring2(String s) {
        int n=s.length();
        Set<Character> set=new HashSet<>();
        int i=0,j=0;
        int maxLen=0;
        while (j<n){
            char c=s.charAt(j);
            while (set.contains(c)){
                set.remove(s.charAt(i));
                i++;
            }
            maxLen=Math.max(maxLen,j-i+1);
            set.add(c);
            j++;
        }
        return maxLen;
    }


    // leetcode54 螺旋矩阵
        public List<Integer> spiralOrder(int[][] matrix) {
            List<Integer>  list=new ArrayList<>();
            int n=matrix.length;
            int m=matrix[0].length;
            if (matrix==null||n==0||m==0){
                return list;
            }
            //螺旋矩阵 定义向四个方向移动
            int  left=0,right=m-1,top=0,bottom=n-1;
            while (left<=right&&top<=bottom){
                //遍历第一层
                for (int column = left; column <=right ; column++) {
                    //第第一层的添加进去
                    list.add(matrix[top][column]);
                }
                //遍历第二层
                for(int row=top+1;row<=bottom;row++){
                    list.add(matrix[row][right]);
                }
                //往右进行遍历
                if (left<right&&top<bottom){
                    //这边i不能等于 left过着top了,因为这个两个点已经遍历过了
                    for (int i = right-1; i >left ; i--) {
                        list.add(matrix[bottom][i]);
                    }
                    for(int i=bottom;i>top;i--){
                        list.add(matrix[i][left]);
                    }
                }
                left++;
                right--;
                top++;
                bottom--;
            }
            return list;
        }


    public List<Integer> inorderTraversal(TreeNode root) {
          List<Integer> list=new ArrayList<>();
          inorder(root, list);
          return list;
    }
    public static void  inorder(TreeNode root,List<Integer> list){
       //中序遍历  左中右

    }
    //直接递归遍历即可
    // if (root==null){
    //            return;
    //        }
    //       inorder(root.left,list);
    //        list.add(root.value);
    //       inorder(root.right,list);

    public int maxDepth(TreeNode root) {
        if (root==null){
            return 0;
        }

        int maxLeft=maxDepth(root.left);
        int maxRight=maxDepth(root.right);

        return 1+Math.max(maxLeft,maxRight);
    }
     //https://leetcode.cn/problems/valid-parentheses/description/
    public boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        int n=s.length();
        // ()  左括号入栈  右入=出栈
        for (int i = 0; i <n ; i++) {
            char c=s.charAt(i);
            if (c=='('||c=='['||c=='{'){
                //入栈
                stack.push(c);
            }else if (c==')'||c==']'||c=='}'){
                if (stack.isEmpty()) return false;
                char pop=stack.pop();
                if ((c==')'&&pop!='(')||(c==']'&&pop!='[')||(c=='}'&& pop!='}')){
                    return false;
                }
            }
        }
        return  stack.isEmpty();
    }

    public List<List<Integer>> threeSum(int[] nums) {
        //result 结果
        List<List<Integer>> result=new ArrayList<>();

        int n=nums.length;
        Arrays.sort(nums);
        for (int i = 0; i <n-1; i++) {
            if (nums[i]>0){
                continue;
            }
            if (i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int left=i+1;
            int right=n-1;
            while (left<right){
                if (nums[i]+nums[left]+nums[right]==0){
                    List tempList=new ArrayList<>();
                    tempList.add(nums[i]);
                    tempList.add(nums[left]);
                    tempList.add(nums[right]);
                    result.add(tempList);
                    left++;
                    right--;
                    //移动左边的
                    while (left<right&&nums[left]==nums[left-1]) {
                        left++;
                    }
                    //移动右边的
                    while (left<right&&nums[right]==nums[right+1]) {
                        right--;
                    }
                }else if (nums[i]+nums[left]+nums[right]>0){
                    right--;
                }else{
                    left++;
                }
            }
        }
        return result;
    }

}
